//题目:
// 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
// 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
// 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。
// 更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
// 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
// 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
// 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
// 给你一个整数数组 nums ，找出 nums 的下一个排列。
// 必须 原地 修改，只允许使用额外常数空间。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<limits.h>
#include<algorithm>

using namespace std;
//代码:
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //但凡存在右边元素大于左边元素的序列，就说明该数组存在“下一个更大的排列”，否则直接升序排nums
        //1.判断该数组是否需要升序排序
        int flag=0;
        for(int left=0,right=1;right<nums.size();left++,right++)
            if(nums[left]<nums[right])flag=1;
        if(flag==0)
        {
            //此时nums是降序，直接逆序即可
            int left=0,right=nums.size()-1;
            while(left<right)
                swap(nums[left++],nums[right--]);
        }
        else 
        {
            //1 2 3 4 ——> 1 2 4 3 ——>1 3 2 4 ——>1 3 4 2 ——>1 4 2 3 ——>1 4 3 2 ——>2 1 3 4 ——>2 1 4 3——>2 3 1 4 ——>2 3 4 1——>2 4 1 3 ——>2 4 3 1 ——>3
            //从后往前来找规律...
            //找到第一个右比左大的元素对
            int right=nums.size()-1,left=right-1;
            while(left>=0)
            {
                if(nums[left]>=nums[right])left--,right--;
                else break;
            }
            //nums[left]就是需要更新的心头，寻找left右边比nums[left]微大的元素
            int _min=nums[left+1],pos=left+1,min_pos=left;
            while(pos<nums.size())
            {
                if(nums[pos]>nums[left] && _min>=nums[pos])_min=nums[pos],min_pos=pos;
                pos++;
            }
            //更新“头”
            swap(nums[left],nums[min_pos]);
            //对头后面的元素排序
            sort(nums.begin()+left+1,nums.end());
        }
    }
};